#include <iostream>
#include <algorithm>

using namespace std;

class GreedyAlgorihm
{
private:
    int boat_capacity;          // 船的载重量
    int antique_num;            // 古董的个数
    int *antique_per_weight;    // 每个古董的重量
    int *optimal_solution;
public:
    GreedyAlgorihm(/* args */);
    GreedyAlgorihm(int capacity, int num);
    ~GreedyAlgorihm();
    int set_boat_capacity(int capacity);
    int set_antique_num(int num);
    int *set_antique_per_weight(int *weight);
    int get_optimal_solution();
};

GreedyAlgorihm::GreedyAlgorihm(/* args */)
{
    return;
}

GreedyAlgorihm::GreedyAlgorihm(int capacity, int num)
{
    this->boat_capacity = capacity;
    this->antique_num = num;
    antique_per_weight = new int[this->antique_num];
}

int *GreedyAlgorihm::set_antique_per_weight(int *weight)
{
    if(NULL == antique_per_weight)
    {
        return NULL;
    }
    for(int i=0; i<antique_num ;i++)
    {
        this->antique_per_weight[i] = weight[i];
    }
    return this->antique_per_weight;
}

int GreedyAlgorihm::set_boat_capacity(int capacity)
{
    this->boat_capacity = capacity;
    return this->boat_capacity;
}

int GreedyAlgorihm::set_antique_num(int num)
{
    this->antique_num = num;
}

int GreedyAlgorihm::get_optimal_solution()
{
    int temp = 0;
    sort(this->antique_per_weight, this->antique_per_weight + this->antique_num);
    for(int i=0; i<this->antique_num; i++)
    {
        temp += this->antique_per_weight[i];
        if(temp > this->boat_capacity)
        {
            temp -= this->antique_per_weight[i];
            break;
        }
    }
    cout << "Heaviest load " << temp << endl;
    return  temp;
}

GreedyAlgorihm::~GreedyAlgorihm()
{
    delete [] antique_per_weight;
}


int main()
{
    GreedyAlgorihm a = GreedyAlgorihm(30, 8);
    int b[8] = {5, 11, 8, 3, 2, 1, 9, 6};
    a.set_antique_per_weight(b);
    a.get_optimal_solution();
    return 0;
}